Código a ejecutar para empezar (de clic en donde en dice “Code”, para desplegar el código, y luego copie y pegue en una sesión abierta de R):
Code
# cambia idioma de la consola de R a español:Sys.setenv(LANG="es")# usar 2 cifras significativas y tiende a evitar # notación científica (ver ayuda de función: `options`): options(digits =2, scipen =999) # cargar librerías: if(!require(igraph)){install.packages("igraph"); library(igraph)}if(!require(sand)){install.packages("sand"); library(sand)}
Grafos y subgrafos
Grafos
Un grafoG = (V, E) es una estructura que consiste de un conjunto de vértices (nodos) V y de un conjunto de aristas (enlaces) E, donde los elementos de E son parejas de la forma e=\{u,v\}, con u,v\in V.
Subgrafos
Un grafo G'=(V',E') es un subgrafo de G=(V,E) si V'\subset V y E'\subset E.
Isomorfismo
Dos grafos que son equivalentes estructuralmente (a pesar de las etiquetas de los vértices) se denominan isomorfos.
Dos grafos G_1 = (V_1, E_1) y G_2 = (V_2, E_2) son isomorfos, lo que se escribe G_1 \equiv G_2, si existe una biyección \varphi:V_1\longrightarrow V_2 tal que \{u,v\}\in E_1 si y solo si \{\varphi(u),\varphi(v)\}\in E_2.
Ejemplo
Si G_1 \equiv G_2, entonces |V_1| = |V_2| y |E_1| = |E_2|.
Si |V_1| \neq |V_2| o |E_1| \neq |E_2|, entonces G_1 \not\equiv G_2.
Si G_1 \equiv G_2 y \{u,v\}\notin E_1, entonces \{\varphi(u),\varphi(v)\}\notin E_2.
# 'method'# auto: Selecciona el mejor procedimiento# direct: Si el grafo tiene tres o cuatro vértices# vf2: Si el grafo es dirigido# bliss: En cualquier otro casoisomorphic(g1, g2, method ="auto")
[1] TRUE
Visualización
# visualizaciónset.seed(123)par(mfrow =c(1,2))plot(g1, vertex.size =15, main ="Grafo 1")plot(g2, vertex.size =15, main ="Grafo 2")
Adyacencia
Vértives adyacentes
Se dice que dos vértices u, v \in V son adyacentes (adjacent), lo que se denota con u\sim v, si u y v están conectados por alguna arista de E.
Vértives asilados
Un vértice v\in V se llama asilado (isolated) si v\not\sim u para todo u\in V.
Un grafo se puede almacenar por medio de una matriz de aristas y una lista de vértices aislados.
Vértices incidentes
Un vértice v \in V es incidente (incident) en una arista e\in E si e = \{v,u\} para algún u\in V.
Grado
El grado (degree) del vértice v\in V se define como el número de aristas incidentes en v.
Para dígrafos, el grado de entrada (in-degree) y el grado de salida (out-degree) del vértice v\in V se definen como el número de aristas que apuntan hacia dentro y hacia fuera de v, respectivamente.
# red dirigidadg <-graph_from_literal(1-+2, 1-+3, 2++3)
# grado de entradadegree(graph = dg, mode ="in")
1 2 3
0 2 2
# grado de salidadegree(graph = dg, mode ="out")
1 2 3
2 1 1
# visualizaciónset.seed(123)plot(dg)
Movimiento
Caminata:
Una caminata (walk) de v_0 a v_\ell de longitud \ell es una secuencia alternante \{v_0,e_1,v_1,e_2,v_2,\ldots,v_{\ell-1},e_\ell,v_\ell\} en la que los puntos extremos de e_i son \{v_{i-1}, v_i\}, con i=1,\ldots,\ell (se pueden repetir vértices y aristas).
Ejemplo
1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 3\, es una caminata abierta.
1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 3\rightarrow 1\, es una caminata cerrada.
Sendero
Un sendero (trail) es una caminata abierta sin aristas repetidas (se pueden repetir vértices).
1\rightarrow 3\rightarrow 8\rightarrow 6\rightarrow 3\rightarrow 2\, es un sendero.
Circuito
Un circuito (circuit) es una caminata cerrada sin aristas repetidas (se pueden repetir vértices).
1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 6\rightarrow 8\rightarrow 3\rightarrow 1\, es un circuito.
Ciclo
Un ciclo (cycle) es una caminata cerrada con al menos tres aristas no repetidas y vértices intermedios distintos.
1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 1\, es un ciclo.
Los grafos que no contienen ciclos se denominan acíclicos (acycle).
Conectividad
Se dice que un vértice v es accesible (reachable) desde otro vértice u si existe una caminata desde u hasta v.
Se dice que un grafo está conectado (connected) si cada vértice es accesible desde todos los demás.
Una componente (component) de un grafo es un subgrafo conectado maximalmente, i.e., un subgrafo al que añadirle cualquier otro vértice arruina la conectividad.